package airthmetic.exercise.dp;

// 经典dp的0-1背包问题
//1.1、问题描述
//      给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。
//      现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？
public class BackPack2 {
    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp(int[] wt, int[] v, int N, int W) {
        /**
         * 因为问题具备重叠子问题和无后效性及最优子结构。 动态规划
         *  重叠子问题：W重量N物品能装多少钱是重叠子问题
         *  无后效性： W重量N物品能装多少钱不会因为后续的选择而失效
         *  最优子结构：W重量N物品最多能装多少钱是可以被后续问题利用计算
         *
         *  1.确定状态参数和选择
         *      先确定什么是原问题 什么是子问题
         *      原问题: W=n N=m
         *      子问题；W=n-1 N=m-1
         *
         *      状态参数：状态参数是在原问题与子问题之间不断变化的值
         *          此题为； W 与 N
         *      选择/决策: 做选择使状态参数不断变化并趋近于原问题的解
         *          选择不同 W 与 N
         *
         *  2.定义 dp table的含义
         *      int[][] dp = new int[N+1][W+1];
         *      dp[i][j] 表示 i个物品放入w重量背包 最多可以装多少价值物品
         *
         *  3.初始化dp table
         *      当背包重量为0时，不管有多少物品都不能装进去  所以背包重量为0时，可以装的物品价值为0
         *      当物品为0个时，不管背包有多少容量，最终背包的物品价值都为0
         *
         *  4.推导状态转移公式
         *      for(int i=1; i<=W; i++){
         *          for(int j=1; i<=N; j++){
         *              // 不能装第j个物品到背包
         *              if(v[j-1] > wt[i-1]){
         *                  dp[i][j] = dp[i][j-1];
         *              }else{
         *                  dp[i][j] = dp[i-1][wt[j-1] - W] + v[j-1];
         *              }
         *          }
         *      }
         *
         */
         int[][] dp = new int[N+1][W+1];
         for(int i=0; i<N+1; i++){
             dp[i][0] = 0;
         }
         for(int j=0; j<W+1; j++){
             dp[0][j] = 0;
         }
        for(int i=1; i<=N; i++){
            for(int j=1; j<=W; j++){
                if( wt[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-wt[i-1]] + v[i-1]);
                }
            }
        }


        return dp[N][W];
    }


    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] wt = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack2().dp(wt,v,N,W));
    }
}
